﻿#define _CRT_SECURE_NO_WARNINGS 1
//最⼩覆盖⼦串（hard）:https://leetcode.cn/problems/minimum-window-substring/
//v1:
class Solution {
public:
    string minWindow(string s, string t) {


        unordered_map<char, int> hash1;
        unordered_map<char, int> hash2;
        string str;
        int ret = INT_MAX;
        int begin = -1;
        int num = t.size();
        for (auto a : t)
        {
            hash1[a]++;
        }

        int left = 0;
        while (left < s.size())
        {
            if (hash1.count(s[left]))  break;
            left++;
        }

        for (int right = left, count = 0; right < s.size(); right++)
        {

            char in = s[right];
            hash2[in]++;
            if (hash1.count(in) && hash2[in] <= hash1[in])   count++;

            while (count == num)
            {
                if (ret > right - left + 1)
                {
                    ret = right - left + 1;
                    // str=s.substr(left,right-left+1);  //大量深拷贝会超限
                    begin = left;
                }

                char out = s[left];
                if (hash1.count(out) && hash2[out] <= hash1[out])   count--;
                hash2[out]--;   left++;
            }

        }

        if (begin == -1)
            return "";
        else
            return s.substr(begin, ret);

    }
};

//v2:
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hash1;
        unordered_map<char, int> hash2;
        int ret = INT_MAX;
        int kind = 0;
        int begin = -1;
        for (auto a : t)
        {
            if (hash1[a]++ == 0)  kind++;
        }

        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            hash2[in]++;
            if (hash2[in] == hash1[in])   count++;

            while (count == kind)
            {
                if (ret > right - left + 1)
                {
                    ret = right - left + 1;
                    begin = left;
                }

                char out = s[left];
                if (hash1[out] == hash2[out])   count--;
                hash2[out]--;   left++;
            }
        }

        if (begin == -1)
            return "";
        else
            return s.substr(begin, ret);
    }
};

//两种方法其实差不多，只是细节出来不一样